
/**11. 盛最多水的容器
 * - 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 * - 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * - 返回容器可以储存的最大水量。
 */
export function maxArea(height: number[] = [1, 8, 6, 2, 5, 4, 8, 3, 7]): number {
    //贪心算法：因为最大的面积，需要宽和高相互搭配，那么我们可以尽可能选择两根最高的为基准，然后尽可能找更远的那根，找到最大的面积
    let left = 0
    let right = height.length - 1
    let max = 0
    while (left < right) {
        max = Math.max(max, (right - left) * Math.min(height[left], height[right]))

        if (height[left] < height[right]) {//如果左侧的矮，左侧就移动，找新的高度
            left++
        } else {//如果右侧的矮，右侧就移动，找个更高的
            right--
        }
    }

    return max
}
/**12. 整数转罗马数字 
 * - 具体描述看 https://leetcode.cn/problems/integer-to-roman/description
 */
export function intToRoman(num: number = 1994): string {
    const map = new Map<number, string>([
        [1000, 'M'],
        [900, "CM"],
        [500, 'D'],
        [400, "CD"],
        [100, 'C'],
        [90, "XC"],
        [50, 'L'],
        [40, "XL"],
        [10, 'X'],
        [9, 'IX'],
        [5, 'V'],
        [4, "IV"],
        [1, 'I'],
    ])
    let res = ''
    //遍历map （按照插入顺序，我是按照从大到小插入的）
    map.forEach((value, key, _map) => {
        while (num >= key) { //贪心：从大的开始放，放不下了才放小的
            res += value
            num -= key
        }
    })
    return res
}
/**53. 最大子数组和 
 * - 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
 * - 子数组 是数组中的一个连续部分。
 */
export function maxSubArray(nums: number[]): number {
    //局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小
    let res = -Infinity
    let nowCount = 0
    for (let i = 0; i < nums.length; i++) {
        nowCount += nums[i]
        if (nowCount > res) res = nowCount
        if (nowCount < 0) nowCount = 0
    }
    return res
};